package com.zjsru.leetcode75.level1.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-12-11
 * 最大层内元素和
 */
public class MaxLevelSum {

    /**
     * 主
     * \
     * 输入：root = [1,7,0,7,-8,null,null]
     * 输出：2
     * 解释：
     * 第 1 层各元素之和为 1，
     * 第 2 层各元素之和为 7 + 0 = 7，
     * 第 3 层各元素之和为 7 + -8 = -1，
     * 所以我们返回第 2 层的层号，它的层内元素之和最大。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TreeNode tree = new TreeNode(1, new TreeNode(7, new TreeNode(7), new TreeNode(-8)), new TreeNode(0));
        MaxLevelSum maxLevelSum = new MaxLevelSum();
        System.out.println(maxLevelSum.maxLevelSum(tree));
    }

    /**
     * 总和
     */
    private List<Integer> sum = new ArrayList<Integer>();

    /**
     * 最大等级总和
     * 广度优先搜索
     * @param root 根
     * @return int
     */
    public int maxLevelSum(TreeNode root) {
        this.dfs(root,0);
        int ans = 0;
        for (int i = 0; i < sum.size(); i++) {
            //更新最大值的最小下标
            if(sum.get(i) > sum.get(ans)){
                ans = i;
            }
        }
        //下标为0，层数是从1开始的，所以加1
        return ans + 1;
    }

    /**
     * dfs
     * 分层来获取sum值
     * @param root  根
     * @param level 级别
     */
    private void dfs(TreeNode root, int level) {
        //层数与sum的数量相同，则将当前的val放入
        if (level == sum.size()) {
            sum.add(root.val);
        } else {
            //同一层的情况下，重新设置当前节点大小
            sum.set(level, sum.get(level) + root.val);
        }
        //左节点计数,进入下一层
        if (root.left != null) {
            this.dfs(root.left, level + 1);
        }
        //右节点计数,进入下一层
        if (root.right != null) {
            this.dfs(root.right, level + 1);
        }
    }

}
